package one.four.twenty;

import java.util.Arrays;

public class Bitonic {

	public static int bi(int[] a, int k) {
		int l = 0;
		int r = a.length - 1;

		while (l <= r) {
			int m = (l + r) / 2;
			if (a[m] == k) {
				return m;
			}
			if (k < a[m]) {
				r = m - 1;
			} else {
				l = m + 1;
			}
			//System.out.println("*");
		}
		return -1;
	}

	public static int bito(int[] a, int k) {
		int l = 0;
		int r = a.length - 1;

		int id = -1;
		ot: while (l <= r) {
			int m = (l + r) / 2;
			if (a[m] > a[m + 1] && a[m] > a[m - 1]) {
				id = m;
				break ot;
			}
			if (a[m] < a[m + 1] && a[m] > a[m - 1]) {
				l = m + 1;
			}
			if (a[m] > a[m + 1] && a[m] < a[m - 1]) {
				r = m - 1;
			}
		}

		//System.out.println(id);
		int[] r0 = Arrays.copyOfRange(a, 0, id + 1);
		int[] r1 = Arrays.copyOfRange(a, id + 1, a.length);
		int[] r2 = new int[r1.length];
		for (int i = 0; i < r1.length; i++) {
			r2[i] = r1[r1.length - 1 - i];
		}
		//System.out.println(Arrays.toString(r0));
		//System.out.println(Arrays.toString(r2));

		int res = bi(r0, k);
		if (res == -1) {
			res = bi(r2, k);
			res = r0.length + r2.length - 1 - res;
		}
		return res;
	}

	public static void main(String[] args) {
		int[] a = { 5, 6, 7, 8, 9, 3, 2, 1 };
		int r = bito(a, 1);

		System.out.println(r);
	}

}
